home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / zip.zip / IM_LM.ASM < prev    next >
Assembly Source File  |  1992-09-22  |  10KB  |  284 lines
  1. ;
  2. ; Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  3. ; Permission is granted to any individual or institution to use, copy, or
  4. ; redistribute this software so long as all of the original files are included
  5. ; unmodified, that it is not sold for profit, and that this copyright notice
  6. ; is retained.
  7. ;
  8.  
  9. ; im_lm.asm by Jean-loup Gailly.
  10.  
  11. ;im_lm.asm, optimized version of longest_match() and lm_process() in im_lmat.c
  12. ; Must be assembled with masm -ml. To be used only with C small model or
  13. ; compact model. This file is only optional. If you don't have masm, use the
  14. ; C version (add -DNO_ASM to CFLAGS in makefile.dos and remove im_lm.obj
  15. ; from OBJI).
  16. ;
  17. ; Turbo C 2.0 does not support static allocation of far data in
  18. ; the small model. So TC 2.0 users must assemble this with:
  19. ;   tasm -ml -DDYN_ALLOC im_lm;
  20. ; OS/2 users must assemble this with -DOS2 -ml. To simplify the code,
  21. ; the option -DDYN_ALLOC is not supported for OS/2.
  22.         name    im_lm
  23.  
  24. ifndef DYN_ALLOC
  25.         extrn   _prev         : word
  26.         extrn   _next         : word
  27.         prev    equ  _prev
  28.         next    equ  _next
  29. load_es_prev macro
  30.         mov     cx,seg _prev
  31.         mov     es,cx
  32. endm
  33. load_ds_next macro
  34.         mov     si,seg _next
  35.         mov     ds,si
  36. endm
  37. endif
  38.  
  39. _BSS    segment  word public 'BSS'
  40.         extrn   _window       : byte
  41.         extrn   _match_length : word
  42.         extrn   _start_length : word
  43.         extrn   _strstart     : word
  44.         extrn   _strsize      : word
  45.         extrn   _ins_h        : word
  46.         extrn   _h_shift      : byte
  47.         extrn   _checkpoint   : word
  48.         extrn   _bufsize      : word
  49.         extrn   _max_chain_length : word
  50.         extrn   _min_match_length : word
  51. ifdef DYN_ALLOC
  52.         extrn   _prev         : word
  53.         extrn   _next         : word
  54.         prev    equ 0         ; offset normalized to zero (except for OS/2)
  55.         next    equ 0         ; offset normalized to zero (except for OS/2)
  56. load_es_prev macro
  57.         mov     es,_prev[2]   ; warning: the offset should be added under OS/2
  58. endm
  59. load_ds_next macro
  60.         mov     ds,_next[2]   ; warning: the offset should be added under OS/2
  61. endm
  62. endif
  63.         cur_best dw 1 dup(?)  ; best match within longest_match
  64. _BSS    ends
  65.  
  66. DGROUP  group _BSS
  67.  
  68. _TEXT   segment word public 'CODE'
  69.         assume  cs: _TEXT, ds: DGROUP, ss: DGROUP
  70.  
  71.         extrn   _write_match : near
  72.  
  73.         BSZ          equ 4096           ; keep consistent with tailor.h
  74.         WSIZE        equ 8192           ; keep consistent with im_lmat.c
  75.         NIL          equ (WSIZE+BSZ)
  76.         MAX_DIST     equ NIL
  77.         MAX_LENGTH   equ 320            ; keep consistent with im_lmat.c
  78.         HASH_MASK    equ 16383          ; (1<<14)-1
  79.  
  80. ; Process a block of characters already inserted in the window
  81. ; IN assertion: count > 0
  82.         public _lm_process
  83. _lm_process  proc near
  84.         push    bp
  85.         mov     bp,sp
  86.         push    di
  87.         push    si
  88.  
  89.         count   equ word ptr [bp+4]
  90. ;       delete_point equ ax
  91. ;       ins_h        equ bx
  92. ;       h_shift      equ cl
  93. ;       count        equ dx
  94. ;       cur_match    equ si
  95. ;       strstart     equ di
  96. ;       min_match_length equ bp
  97.  
  98.         mov     dx,count
  99.         mov     bx,_ins_h
  100.         mov     di,_strstart
  101.         lea     ax,[di+MAX_LENGTH-1]
  102.         sub     ax,_bufsize
  103.         jae     del_ok
  104.         add     ax,MAX_DIST
  105. del_ok: shl     ax,1                    ;delete_point as word index
  106.         load_es_prev
  107.         mov     cl,_h_shift
  108.         load_ds_next
  109.         assume  ds: nothing
  110.         jmp     short insert
  111.  
  112. start_overflow:
  113.         sub     di,di                   ;strstart = 0
  114.         sub     ss:_checkpoint,MAX_DIST
  115.         jmp     short check_count
  116. del_overflow:
  117.         mov     ax,-2                   ;delete_point = 0
  118. main_loop:
  119.         add     ax,2                    ;delete_point++ (word index)
  120.         cmp     ax,2*MAX_DIST
  121.         je      del_overflow
  122.         xchg    ax,si                   ;si=2*delete_point
  123.         mov     bp,next[si]
  124.         shl     bp,1
  125.         mov     es:prev[bp],NIL
  126.         xchg    ax,si                   ;ax=2*delete_point
  127.  
  128.         inc     di                      ;strstart++
  129.         cmp     di,MAX_DIST
  130.         je      start_overflow
  131. check_count:
  132.         dec     dx                      ;count--
  133.         jz      end_proc_ok
  134. insert:
  135.         shl     bx,cl                   ;ins_h <<= h_shift
  136.         mov     bp,ss:_min_match_length
  137.         xor     bl,_window[di+bp-1]     ;ins_h ^= window[s+min_match_length-1]
  138.         and     bx,HASH_MASK
  139.         add     bx,MAX_DIST+1
  140.         shl     bx,1                    ;word index
  141.         mov     si,es:prev[bx]          ;cur_match = match_head[ins_h]
  142.         mov     es:prev[bx],di          ;prev[ins_h+MAX_DIST+1] = strstart
  143.         shr     bx,1                    ;bx = ins_h + MAX_DIST + 1
  144.         shl     di,1                    ;di = strstart as word index
  145.         mov     next[di],bx
  146.         sub     bx,MAX_DIST+1           ;bx = ins_h
  147.         mov     es:prev[di],si          ;prev[s] = cur_match
  148.         shr     di,1                    ;di = strstart
  149.         shl     si,1
  150.         mov     next[si],di             ;next[cur_match] = strstart
  151.         cmp     di,ss:_checkpoint
  152.         jne     main_loop
  153.  
  154.         push    ax
  155.         push    bx
  156.         push    dx
  157.         mov     ax,ss
  158.         mov     ds,ax
  159.         assume  ds: DGROUP
  160.         mov     _match_length,0
  161.         mov     _strstart,di
  162.         shr     si,1                    ;si = cur_match
  163.         cmp     si,NIL                  ;cur_match == NIL ?
  164.         je      call_write
  165.         call    _longest_match          ;returns best_match in si
  166. call_write:
  167.         push    _match_length
  168.         push    si                      ;best_match or NIL
  169.         call    _write_match
  170.         add     sp,4
  171.         pop     dx
  172.         pop     bx
  173.         or      al,al
  174.         jnz     failure
  175.         pop     ax
  176.         load_es_prev
  177.         mov     cl,_h_shift
  178.         load_ds_next
  179.         assume  ds: nothing
  180.         jmp     main_loop
  181. end_proc_ok:
  182.         mov     ax,ss
  183.         mov     ds,ax
  184.         assume  ds: DGROUP
  185.         sub     ax,ax
  186.         mov     _strstart,di
  187. end_proc:
  188.         mov     _ins_h,bx
  189.         pop     si
  190.         pop     di
  191.         pop     bp
  192.         ret
  193. failure:
  194.         add     sp,2                    ;skip pushed ax
  195.         jmp     short end_proc
  196.  
  197. _lm_process  endp
  198.  
  199. ; Find the longest match starting at the given string. Return its position
  200. ; and set its length in match_length. Matches shorter or equal to
  201. ; start_length are discarded, in which case match_length is unchanged
  202. ; and the result position is NIL.
  203. ; IN assertions: cur_match is the head of the hash chain for the current
  204. ;    string (strstart) and is not NIL, start_length >= 1.
  205. ;    registers: es points to the base of the prev array (preserved)
  206. ;               si = cur_match and return value
  207. ;               di = strstart
  208.  
  209. ; IPos longest_match(cur_match)
  210.  
  211.         public _longest_match
  212. _longest_match  proc near
  213.  
  214.         push    bp
  215.         push    di
  216.  
  217. ;       match        equ si
  218. ;       scan         equ di
  219. ;       chain_count  equ bp
  220. ;       ma_length    equ bx
  221.  
  222.         lea     di,_window[di+2]        ; di = window + strstart + 2
  223.         mov     cur_best,NIL
  224.         mov     bp,_max_chain_length    ; chain_count = max_chain_length
  225.         mov     bx,_start_length        ; ma_length = start_length
  226.         mov     ax,[bx+di-3]            ; ax = scan[ma_length-1..ma_length]
  227.         mov     cx,[di-2]               ; cx = scan[0..1]
  228.         jmp     short do_scan
  229.  
  230.         even                            ; align destination of branch
  231. long_loop:
  232. ; at this point, di == scan+2, si = cur_match
  233.         mov     ax,[bx+di-3]            ; ax = scan[ma_length-1..ma_length]
  234.         mov     cx,[di-2]               ; cx = scan[0..1]
  235. short_loop:
  236.         dec     bp                      ; --chain_count
  237.         jz      the_end
  238. ; at this point, di == scan+2, si = cur_match,
  239. ; ax = scan[ma_length-1..ma_length] and cx = scan[0..1]
  240.         shl     si,1                    ; cur_match as word index
  241.         mov     si,es:prev[si]          ; cur_match = prev[cur_match]
  242.         cmp     si,NIL
  243.         je      the_end
  244. do_scan:
  245.         cmp     ax,word ptr _window[bx+si-1] ; check match at ma_length-1
  246.         jne     short_loop
  247.         cmp     cx,word ptr _window[si]      ; check min_match_length match
  248.         jne     short_loop
  249.         mov     dx,si                   ; dx = cur_match
  250.         lea     si,_window[si+2]        ; si = match
  251.         mov     ax,di                   ; ax = scan+2
  252.         mov     cx,ds
  253.         mov     es,cx
  254.         mov     cx,(MAX_LENGTH-2)/2     ; scan for at most MAX_LENGTH bytes
  255.         repe    cmpsw                   ; loop until mismatch
  256.         load_es_prev                    ; reset es to address the prev array
  257.         mov     cl,[di-2]               ; mismatch on first or second byte?
  258.         sub     cl,[si-2]               ; dl = 0 if first bytes equal
  259.         xchg    ax,di                   ; di = scan+2, ax = end of scan
  260.         sub     ax,di                   ; ax = len
  261.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  262.         adc     ax,0                    ; ax = carry ? len+1 : len
  263.         mov     si,dx                   ; si = cur_match
  264.         cmp     ax,bx                   ; len > ma_length ?
  265.         jle     long_loop
  266.         mov     cur_best,si             ; cur_best = cur_match
  267.         mov     bx,ax                   ; bx = ma_length = len
  268.         cmp     ax,_strsize             ; len >= strsize ?
  269.         jle     long_loop
  270. the_end:
  271.         cmp     bx,_start_length        ; ma_length > start_length ?
  272.         jle     return
  273.         mov     _match_length,bx        ; match_length = ma_length
  274. return:
  275.         mov     si,cur_best             ; result = cur_best
  276.         pop     di
  277.         pop     bp
  278.         ret
  279.  
  280. _longest_match  endp
  281.  
  282. _TEXT   ends
  283. end
  284.